﻿using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Merge_Sort
{
    public class MergeSort
    {
        public int[] arr;
        private int limit;

        public MergeSort(int[] arra, int p_limit)
        {
            arr = arra;
            limit = p_limit;
        }
        
        public void seqSort()
        {
            arr = SeqSort1(arr);
        }

        public void parSort()
        {
            arr = parSort1(arr,0);
        }

        private int[] parSort1(int[] a,int level)
        {
            
                if (a.Length < 2)
                    return a;
                int middle = a.Length / 2;
                int[] left = new int[middle];
                for (int i = 0; i < left.Length; i++)
                {
                    left[i] = a[i];
                }
                int[] right = new int[a.Length - middle];
                for (int i = 0; i < right.Length; i++)
                {
                    right[i] = a[i + middle];
                }
                if (/*a.Length > 100000||*/  level<limit) { 
                var t1 = Task.Factory.StartNew(() => left = parSort1(left,level +1));
                var t2 = Task.Factory.StartNew(() => right = parSort1(right,level +1));

                Task.WaitAll(t1, t2);}
                else
                {
                    left = SeqSort1(left);
                    right = SeqSort1(right);
                }


                //left = SeqSort1(left);
                //right = SeqSort1(right);

                int LeftIdx = 0;
                int RightIdx = 0;

                int[] sorted = new int[a.Length];
                for (int k = 0; k < a.Length; k++)
                {
                    if (RightIdx == right.Length || (LeftIdx < left.Length && left[LeftIdx] <= right[RightIdx]))
                    {
                        sorted[k] = left[LeftIdx];
                        LeftIdx++;
                    }
                    else if (LeftIdx == left.Length || (RightIdx < right.Length && right[RightIdx] <= left[LeftIdx]))
                    {
                        sorted[k] = right[RightIdx];
                        RightIdx++;
                    }
                }
                return sorted;
            
        }

        private int[] SeqSort1(int[] a)
        {
            if (a.Length <2)
                return a;
            int middle = a.Length / 2;
            int[] left = new int[middle];
            for (int i = 0; i < left.Length; i++)
            {
                left[i] = a[i];
            }
            int[] right = new int[a.Length - middle];
            for (int i = 0; i < right.Length; i++)
            {
                right[i] = a[i + middle];
            }
            left = SeqSort1(left);
            right = SeqSort1(right);

            int LeftIdx = 0;
            int RightIdx = 0;

            int[] sorted = new int[a.Length];
            for (int k = 0; k < a.Length; k++)
            {
                if (RightIdx == right.Length || (LeftIdx < left.Length && left[LeftIdx] <= right[RightIdx]))
                {
                    sorted[k] = left[LeftIdx];
                    LeftIdx++;
                }
                else if (LeftIdx == left.Length || (RightIdx < right.Length && right[RightIdx] <= left[LeftIdx]))
                {
                    sorted[k] = right[RightIdx];
                    RightIdx++;
                }
            }
            return sorted;
        }
    }
}
